#include <iostream>
#include <fstream>
#include <vector>
#include<functional>
#include<algorithm>
#include<vector>
#include <ctime>


using namespace std;
template <typename Comparable>
class BinarySearchTree
{
private:
	//定义BinaryNode
	struct BinaryNode
	{
		Comparable element;
		BinaryNode *left;
		BinaryNode *right;

		BinaryNode(const Comparable & theElement, BinaryNode *lt, BinaryNode *rt) :element{ theElement }, left{ lt }, right{ rt }{ }

		BinaryNode(Comparable && theElement, BinaryNode *lt, BinaryNode *rt) :element{ theElement }, left{ lt }, right{ rt }{ }

	};

	BinaryNode *root;
private:
	//将全部函数复制于此处。
	void insert(const Comparable & x, BinaryNode * & t)
	{
		if (t == nullptr)
			t = new BinaryNode(x, nullptr, nullptr);
		else if (x < t->element)
			insert(x, t->left);
		else if (t->element < x)
			insert(x, t->right);
		else
			;//do nothing
	};
	void insert(Comparable && x, BinaryNode * & t)
	{
		if (t == nullptr)
			t = new BinaryNode{ std::move(x),nullptr,nullptr };
		else if (x < t->element)
			insert(std::move(x), t->left);
		else if (t->element < x)
			insert(std::move(x), t->right);
		else
			;//do  nothing

	};
	void remove(const Comparable & x, BinaryNode * & t)
	{
		if (t == nullptr)
			return;
		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr && t->right != nullptr)
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			BinaryNode * oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}
	};

	BinaryNode * findMax(BinaryNode *t) const //递归型
	{
		if (t == nullptr)
			return nullptr;
		if (t->right == nullptr)
			return t;
		return findMax(t->right);
	};
	BinaryNode * findMin(BinaryNode *t) const //递归型
	{
		if (t == nullptr)
			return nullptr;
		if (t->left == nullptr)
			return t;
		return findMin(t->left);
	};

	bool contains(const Comparable & x, BinaryNode *t) const
	{
		if (t == nullptr)
			return false;
		else if (x < t->element)
			return contains(x, t->left);
		else if (t->element < x)
			return contains(x, t->right);
		else
			return true;
	};
	void makeEmpty(BinaryNode * & t)
	{
		if (t != nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	};
	void printTree(BinaryNode *t, ostream & out)const
	{
		if (t != nullptr)
		{
			printTree(t->left, out);
			out << t->element << endl;
			printTree(t->right, out);
		}
	};

	//clone 
	BinaryNode * clone(BinaryNode *t)const
	{
		if (t == nullptr)
			return nullptr;
		else
			return new BinaryNode{ t->element,clone(t->left),clone(t->right) };
	};
	//中序遍历并覆盖vector，为HOMEWORK ONE 和HOMEWORK TWO做准备。
	vector<Comparable> cover(BinaryNode *t, vector<Comparable> data)const
	{
		if (t == nullptr)
		{
			return data;
		}
		data = cover(t->left, data);
		data.push_back(t->element);
		data = cover(t->right, data);
		return data;

	};
	//对vector中元素乱序排列，为HOMEWORK2做准备。
	vector<Comparable> random(vector<Comparable> data)
	{
		srand((unsigned int)time(0));
		random_shuffle(data.begin(), data.end());
		return data;
	};
public:
	///构造函数。
	BinarySearchTree() //这里貌似有点问题！
	{
		//BinaryNode(NULL, nullptr, nullptr);
		root = nullptr;
	};
	/*BinarySearchTree(Comparable d)//构造时没有把d包含进树里。有点问题！
	{
		BinaryNode(d, nullptr, nullptr);
	};*/
	BinarySearchTree(const BinarySearchTree & rhs) : root{ nullptr }
	{
		root = clone(rhs.root);
	};
	BinarySearchTree(BinarySearchTree && rhs) : root{ nullptr }
	{
		root = clone(rhs.root);
	};

	~BinarySearchTree()
	{
		makeEmpty();
	};

	///
	//find the minimum.
	const Comparable & findMin() const
	{
		return findMin(root)->element;
	};

	//find the maximum.
	const Comparable & findMax()const
	{
		return findMax(root)->element;
	};

	//确定是否包含x值。
	bool contains(const Comparable & x) const
	{
		return contains(x, root);
	};
	//判断是否为空。
	bool isEmpty() const
	{
		if (root != nullptr)
			return false;
		else
			return true;
	};
	//输出。
	void printTree(ostream & out = cout) const
	{
		if (isEmpty())
			out << "Empty tree" << endl;
		else
			printTree(root, out);
	};

	///
	//创建空树。
	void makeEmpty()
	{
		makeEmpty(root);
	};
	//插入x值。
	void insert(const Comparable & x)
	{
		insert(x, root);
	};
	//插入x值。
	void insert(Comparable && x)
	{
		insert(x, root);
	};
	//移除x值。
	void remove(const Comparable & x)
	{
		remove(x, root);
	};


	///
	//定义赋值运算符const。
	BinarySearchTree & operator =(const BinarySearchTree & rhs) {};
	//定义赋值运算符。
	BinarySearchTree & operator =(BinarySearchTree && rhs) {};

	///HOMEWORK ONE.
	//对_data中全部元素，从空树开始依次做BST插入，形成二叉搜索树，覆盖在_data中
	vector<Comparable> BST_sort(std::vector<Comparable> &_data)
	{
		int n = _data.size();
		//将data里的数据插入tree.
		for (int i = 0; i < n; i++)
		{
			insert(_data[i]);
		};
		//令tree中的数据覆盖_data.
		_data.clear();
		_data = cover(root, _data);
		//return the final _data.
		return _data;


	};
	///HOMWORK TWO.
	//对 _data 中全部元素, 先进行乱序操作, 然后从空树开始, 依次做 BST 插入, 形成二叉搜索树, 然后中序遍历输出, 覆盖在 _data 中.实现时鼓励采用相关 STL 功能
	vector<Comparable> Randomized_BST_sort(std::vector<Comparable> &_data)
	{
		//对_data中元素乱序排列。
		_data = random(_data);
		//输出乱序后的vector.
		cout << "乱序后的vector是:  ";
		for (int i = 0; i < _data.size(); i++)
		{
			cout << _data[i] << "     ";
		}
		cout << endl;
		//对乱序后的vector操作
		_data = BST_sort(_data);
		return _data;
	};

}; 
